Masala #1146
Radio
Shahar to’g’ri chiziqdan iborat, va bu shaharda mahalliy aholini yangiliklardan xabardor qilish uchun \(N\) ta Radio o’rnatilgan. Har bir radioning ovoz balandligi \(K\) ga teng. Radioda yangilik eshittirilganda \(A\)- koordinatada bo’lgan uyga \(B\)-koordinatada joylashtirilgan radioning ovozi \(max(K-|A-B|, 0)\) balandlikda eshitiladi. Sizga \(M\) ta uyning koordinatasi beriladi, har bir uy uchun ungacha yetib kelatidan eng baland radio ovozining balandligini aniqlang.
Kirish oqimining dastlabki satrida uchta butun son, \(N(1 \le N \le 250000)\), \(M(1 \le M \le 250000)\) va \(K(1 \le K \le 10^9)\) sonlari kiritiladi. Ikkinchi satrda \(N\) ta butun son, \(B_i(1 \le i \le N, 0 \le B_i \le 10^9)\) Radiolarning joylashgan koordinatalari kamaymaslik tartibida kiritiladi. Uchinchi satrda M ta butun son, \(A_i(1 \le i \le M, 0 \le A_i \le 10^9)\) uylarning joylashgan koordinatalari kiritiladi.
Chiqish oqimida har bir uy uchun alohida qatorda bittadan butun son, berilgan uyga radioning ovozi qanday balandlikda eshitilishini chop eting.
# | input.txt | output.txt |
---|---|---|
1 |
1 5 10 20 20 15 28 10 32 |
10 5 2 0 0 |
2 |
3 4 100 116 194 258 57 155 222 360 |
41 61 72 0 |